package binary_tree.leetcode.medium;

/**
 * @author bruin_du
 * @description 重构二叉树
 * @date 2022/6/5 10:28
 **/
public class Offer07_BuildTree {
    private int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0) return null;
        return build(preorder,inorder,0,preorder.length - 1);
    }

    private TreeNode build(int[] preorder, int[] inorder, int left, int right) {
        if(left > right) return null;
        int x = find(inorder,preorder[index]);
        TreeNode root = new TreeNode(preorder[index++]);
        root.left = build(preorder, inorder, left, x - 1);
        root.right = build(preorder, inorder, x + 1, right);
        return root;
    }

    private int find(int[] inorder, int i) {
        for (int j = 0; j < inorder.length; j++) {
            if(inorder[j] == i) return j;
        }
        return -1;
    }
}
